package leetcode.code994.RottingOranges;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 01矩阵方式
 *
 * @author Administrator
 *
 */
public class Solution99401 extends RottingOranges {

	@Override
	public int orangesRotting(int[][] grid) {
		int h = grid.length;
		int w = grid[0].length;
		int range = h * w;
		int[][] res = new int[h][w];
		Queue<int[]> q = new LinkedList<>();
		int good = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (grid[i][j] == 2) {
					res[i][j] = 0;
					q.add(new int[] { i, j });
				} else if (grid[i][j] == 1) {
					res[i][j] = range;
					good++;
				} else
					res[i][j] = -1;
			}
		}
		int max = 0;// 最大天数
		while (!q.isEmpty()) {
			int[] p = q.poll();
			int x = p[0];
			int y = p[1];
			int v = res[x][y];
			max = max > v ? max : v;
			int v1 = v + 1;
			if (x - 1 >= 0) {
				if (res[x - 1][y] != -1 && res[x - 1][y] > v1) {
					if (res[x - 1][y] == range)
						good--;
					res[x - 1][y] = v1;
					q.add(new int[] { x - 1, y });
				}
			}
			if (y - 1 >= 0) {
				if (res[x][y - 1] != -1 && res[x][y - 1] > v1) {
					if (res[x][y - 1] == range)
						good--;
					res[x][y - 1] = v1;
					q.add(new int[] { x, y - 1 });
				}
			}
			if (x + 1 < h) {
				if (res[x + 1][y] != -1 && res[x + 1][y] > v1) {
					if (res[x + 1][y] == range)
						good--;
					res[x + 1][y] = v1;
					q.add(new int[] { x + 1, y });
				}
			}
			if (y + 1 < w) {
				if (res[x][y + 1] != -1 && res[x][y + 1] > v1) {
					if (res[x][y + 1] == range)
						good--;
					res[x][y + 1] = v1;
					q.add(new int[] { x, y + 1 });
				}
			}
		}
		return good == 0 ? max : -1;
	}

	public static void main(String[] args) {
		Solution99401 so = new Solution99401();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
